#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 5e5 + 10;

vec pot[N], fa[N];
int n, m, a[N], mx;
ll tr[N];
void add(int x, int v) { for(; x <= n; x += x & -x) tr[x] += v; }
int gf(int x, int t) { return fa[x][t] == t ? t : fa[x][t] = gf(x, fa[x][t]); }
ll query(int x) { ll res = 0; for(; x; x -= x & -x) res += tr[x]; return res; }

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in, m = in;
	rep(i, 1, n) a[i] = in, chkmax(mx, a[i]);
	rep(i, 1, n) {
		int x = a[i];
		rep(j, 1, x) {
			if(j * j > x) break;
			if(x % j) continue;
			pot[j].eb(i);
			if(j * j != x) pot[x / j].eb(i);
		} add(i, x);
	}
	rep(i, 1, mx) {
		pot[i].eb(n + 1); fa[i].resize(pot[i].size());
		iota(fa[i].begin(), fa[i].end(), 0);
	}
	while(m--) {
		int op = in, l = in, r = in, x;
		if(op == 1) {
			x = in; if(x == 1 || x > mx) continue;
			vec &pot = ::pot[x], &fa = ::fa[x];
			int pos = lower_bound(pot.begin(), pot.end(), l) - pot.begin();
			while(pot[pos = gf(x, pos)] <= r) {
				if(a[pot[pos]] % x == 0) add(pot[pos], a[pot[pos]] / x - a[pot[pos]]), a[pot[pos]] /= x;
				if(a[pot[pos]] % x != 0) fa[pos] = pos + 1;
				pos++;
			}
		} else printf("%lld\n", query(r) - query(l - 1));
	}
	return 0;
}
